package com.algorithm7;

import java.util.Arrays;

public class HeapSort {

    private static void heapSort(int[] array){
        for(int i=array.length-1;i>=0;i--){
            Utils.swap(array,0,i);
            heapify(array,0,i);
        }

    }

    private static void buildHeap(int[] array,int len){
        for(int i = array.length/2; i>=0; i--){
            heapify(array,i,len);
        }
    }
    private static void heapify(int[] array,int i,int len){
        int max = i;
        int left = 2*i;
        int right = 2*i+1;
        if(left<len && array[left]>array[max]){
                max = left;
            }
        if(right<len && array[right]>array[max]){
                max = right;
            }
        if(max!=i){
                Utils.swap(array,i,max);
                heapify(array,max,len);
            }


    }
    public static void main(String[] args){
        int[] array = {1,3,5,7,9,2,4,6,8,10};
        buildHeap(array,array.length);
        heapSort(array);
        //int[] array = new int[]{4,3,5,8,9,7,10,6,1,2};
        //quickSort(array,0,array.length-1);
        System.out.println(Arrays.toString(array));
    }
}
